B.1 Field of Invention
This disclosure teaches techniques, methods and systems related in general to the field of information processing. More particularly, the teachings relate to methods, systems, and computer-program products for querying tree-structured databases, Web pages, or XML documents using formalisms or query languages that share certain characteristics and navigational constructs such as path expressions with the standardized XPath 1 formalism [W4] of the World Wide Web Consortium.
B.2 Basic Concepts, Terminology, and Introduction
The reader is assumed to be familiar with XML (cf. [W2]), XPath and, in particular, with standard notions such as axes and location steps in XPath (cf. [W4]). XPath has been proposed by the W3C [W4] primarily as a practical language for selecting nodes from XML document trees. But it is also designed to be used for formulating expressions that evaluate to a string, a number or a boolean value. The importance of XPath stems from    1. its potential application as an XML query language per se and    2. it being at the core of several other XML-related technologies, such as XSLT, XPointer, and XQuery, and the great and well-deserved interest such technologies receive.
B.3 Desirable Properties of Methods and Systems Evaluating Xpath Queries and Xpath Expressions over XML Documents
Since XPath and related technologies will be tested in ever-growing deployment scenarios, its implementations need to scale well both with respect to the size of the XML data and the growing size and intricacy of the queries (usually referred to as combined complexity). In particular, this evaluation should profitably be feasible in polynomial time for any given XML document, any given XPath query or XPath expression and, optionally, any given context.
B.4 References
The following documents provide background information helpful in understanding this disclosure, and to that extent, they are incorporated herein by reference. They are referred to, using the abbreviated notations shown below, in subsequent discussions to indicate specific relevance wherever necessary.